package lt629
/*
629. K个逆序对数组
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 10^9 + 7 的值。
*/
/*
f[i][j] 表示我们使用数字 1,2,⋯,i 的排列构成长度为 i 的数组，
并且恰好包含 j个逆序对的方案数。

在进行状态转移时，我们可以考虑第 i 个元素选取了1,2,⋯,i 中的哪个数字。
假设我们选取了数字k，那么数组的前 i−1 个元素由 1,⋯,k−1 以及 k+1,⋯,i 的某个排列构成。
数组中的逆序对的个数可以看成如下的两部分之和：
	数字 k 与前 i−1 个元素产生的逆对的个数；
	前i−1 个元素「内部」产生的逆序对个数。
对于第一部分而言，
我们可以求出：数字 k 会贡献 i−k 个逆序对，即k+1,⋯,i 与 k 分别产生一个逆序对。
对于第二部分而言，我们希望它能够有 j −(i−k) 个逆序对，这样才能一共有 j 个逆序对。
由于我们关心的是前i−1 个元素「内部」产生的逆序对个数，而逆序对只和元素的「相对大小」有关，因此我们可以：
	1,⋯,k−1 这些元素保持不变；
	k+1,⋯,i 这些素均减少 1，变成k,⋯,i−1。
使得前 i−1 个元素中，任意两个元素的相对大小都不发生变化。
此时，我们的目标变成了「对于 1,2,⋯,i−1，希望它能够有 j−(i−k) 个逆序对」，
这就是动态规划中的子任务 f[i−1][j−(i−k)]。
f[i][j]= 
k=1
∑
i
​	
 f[i−1][j−(i−k)]= 
k=0
∑
i−1
​	
 f[i−1][j−k]

 f[i][j]=f[i][j−1]−f[i−1][j−i]+f[i−1][j]
*/
func kInversePairs(n, k int) int {
    const mod int = 1e9 + 7
    f := [2][]int{make([]int, k+1), make([]int, k+1)}
    f[0][0] = 1
    for i := 1; i <= n; i++ {
        for j := 0; j <= k; j++ {
            cur := i & 1
            prev := cur ^ 1
            f[cur][j] = 0
            if j > 0 {
                f[cur][j] = f[cur][j-1]
            }
            if j >= i {
                f[cur][j] -= f[prev][j-i]
            }
            f[cur][j] += f[prev][j]
            if f[cur][j] >= mod {
                f[cur][j] -= mod
            } else if f[cur][j] < 0 {
                f[cur][j] += mod
            }
        }
    }
    return f[n&1][k]
}
